{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Odd Levels of Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseOddLevels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转二叉树的奇数层"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵 <strong>完美</strong> 二叉树的根节点 <code>root</code> ，请你反转这棵树中每个 <strong>奇数</strong> 层的节点值。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，假设第 3 层的节点值是 <code>[2,1,3,4,7,11,29,18]</code> ，那么反转后它应该变成 <code>[18,29,11,7,4,3,1,2]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>反转后，返回树的根节点。</p>\n",
    "\n",
    "<p><strong>完美</strong> 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。</p>\n",
    "\n",
    "<p>节点的 <strong>层数</strong> 等于该节点到根节点之间的边数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/28/first_case1.png\" style=\"width: 626px; height: 191px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,3,5,8,13,21,34]\n",
    "<strong>输出：</strong>[2,5,3,8,13,21,34]\n",
    "<strong>解释：</strong>\n",
    "这棵树只有一个奇数层。\n",
    "在第 1 层的节点分别是 3、5 ，反转后为 5、3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/28/second_case3.png\" style=\"width: 591px; height: 111px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [7,13,11]\n",
    "<strong>输出：</strong>[7,11,13]\n",
    "<strong>解释：</strong> \n",
    "在第 1 层的节点分别是 13、11 ，反转后为 11、13 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]\n",
    "<strong>输出：</strong>[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]\n",
    "<strong>解释：</strong>奇数层由非零值组成。\n",
    "在第 1 层的节点分别是 1、2 ，反转后为 2、1 。\n",
    "在第 3 层的节点分别是 1、1、1、1、2、2、2、2 ，反转后为 2、2、2、2、1、1、1、1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数目在范围 <code>[1, 2<sup>14</sup>]</code> 内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>root</code> 是一棵 <strong>完美</strong> 二叉树</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-odd-levels-of-binary-tree](https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-odd-levels-of-binary-tree](https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,5,8,13,21,34]', '[7,13,11]', '[0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1,node2,is_ood_level):\n",
    "            if node2 is None:return\n",
    "            if is_ood_level:node1.val,node2.val = node2.val,node1.val\n",
    "            dfs(node1.left,node2.right,not is_ood_level)\n",
    "            dfs(node1.right,node2.left,not is_ood_level)\n",
    "        dfs(root.left,root.right,True)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1,node2,is_ood_level):\n",
    "            if node1 is None:return\n",
    "            if is_ood_level:node1.val,node2.val = node2.val,node1.val\n",
    "            dfs(node1.left,node2.right,not is_ood_level)\n",
    "            dfs(node1.right,node2.left,not is_ood_level)\n",
    "        dfs(root.left,root.right,True)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "        isOdd = False\n",
    "        while len(q) > 0:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.left is not None:\n",
    "                    q.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    q.append(node.right)\n",
    "            if isOdd:\n",
    "                for i in range (len(tmp) // 2):\n",
    "                    nodex, nodey = tmp[i], tmp[len(tmp) - 1 - i]\n",
    "                    nodex.val, nodey.val = nodey.val, nodex.val\n",
    "            isOdd ^= True\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        def is_odd_reverse(left, right, is_odd_level):\n",
    "            if not left: return\n",
    "            if is_odd_level: \n",
    "\n",
    "                left.val,right.val = right.val,left.val\n",
    "           \n",
    "            is_odd_reverse(left.left,right.right,not is_odd_level)\n",
    "            is_odd_reverse(left.right,right.left,not is_odd_level)\n",
    "\n",
    "        is_odd_reverse(root.left, root.right, True)\n",
    "        return root\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, level = [root], True\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            if level:\n",
    "                for i in range(len(q) // 2):\n",
    "                    x, y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            level = not level\n",
    "        return root\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q,level=[root],0\n",
    "        while q[0].left:\n",
    "            q=list(chain.from_iterable((node.left,node.right)for node in q))\n",
    "            if level==0:\n",
    "                for i in range(len(q)//2):\n",
    "                    x,y=q[i],q[len(q)-1-i]\n",
    "                    x.val,y.val=y.val,x.val\n",
    "            level^=1\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def reverse(leftNode:Optional[TreeNode],rightNode:Optional[TreeNode]):\n",
    "            temp=leftNode.left\n",
    "            leftNode.left=rightNode.left\n",
    "            rightNode.left=temp\n",
    "\n",
    "            temp=leftNode.right\n",
    "            leftNode.right=rightNode.right\n",
    "            rightNode.right=temp\n",
    "\n",
    "            return rightNode,leftNode\n",
    "\n",
    "        dueue=[root]\n",
    "        level=1\n",
    "\n",
    "        while dueue[0].left:\n",
    "            temp=[]\n",
    "            for q in dueue:\n",
    "                temp.append(q.left)\n",
    "                temp.append(q.right)\n",
    "            \n",
    "            if level % 2==1: #交换\n",
    "                l=len(dueue)\n",
    "                if l==1:\n",
    "                    dueue[0].left,dueue[0].right=reverse(dueue[0].left,dueue[0].right)\n",
    "                else:\n",
    "                    for i in range(l//2):\n",
    "                        dueue[i].left,dueue[l-i-1].right=reverse(dueue[i].left,dueue[l-i-1].right)\n",
    "                        dueue[i].right,dueue[l-i-1].left=reverse(dueue[i].right,dueue[l-i-1].left)\n",
    "            level+=1\n",
    "            dueue=temp\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "        depth = 0\n",
    "        vals = []\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            # print(\"depth\", depth)\n",
    "            n = len(tmp)\n",
    "            for i in range(n):\n",
    "                if tmp[i].left:\n",
    "                    q.append(tmp[i].left)\n",
    "                    q.append(tmp[i].right)\n",
    "                    if depth & 1 == 0:\n",
    "                        vals.append(tmp[i].left.val)\n",
    "                        vals.append(tmp[i].right.val)\n",
    "                if depth & 1:\n",
    "                    tmp[i].val = vals[n - 1 - i]\n",
    "            # print(q, vals)\n",
    "            if depth & 1:\n",
    "                vals = []\n",
    "            depth += 1\n",
    "            # print(q, vals)\n",
    "        return root\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def reverse(leftNode:Optional[TreeNode],rightNode:Optional[TreeNode]):\n",
    "            temp=leftNode.left\n",
    "            leftNode.left=rightNode.left\n",
    "            rightNode.left=temp\n",
    "\n",
    "            temp=leftNode.right\n",
    "            leftNode.right=rightNode.right\n",
    "            rightNode.right=temp\n",
    "\n",
    "            return rightNode,leftNode\n",
    "\n",
    "        dueue=[root]\n",
    "        level=1\n",
    "\n",
    "        while dueue[0].left:\n",
    "            temp=[]\n",
    "            for q in dueue:\n",
    "                temp.append(q.left)\n",
    "                temp.append(q.right)\n",
    "            \n",
    "            if level % 2==1: #交换\n",
    "                l=len(dueue)\n",
    "                if l==1:\n",
    "                    dueue[0].left,dueue[0].right=reverse(dueue[0].left,dueue[0].right)\n",
    "                else:\n",
    "                    for i in range(l//2):\n",
    "                        dueue[i].left,dueue[l-i-1].right=reverse(dueue[i].left,dueue[l-i-1].right)\n",
    "                        dueue[i].right,dueue[l-i-1].left=reverse(dueue[i].right,dueue[l-i-1].left)\n",
    "            level+=1\n",
    "            dueue=temp\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        s = [root]\n",
    "        l = 0\n",
    "        while s[0].left:\n",
    "            ns = []\n",
    "            for i in s:\n",
    "                ns.append(i.left)\n",
    "                ns.append(i.right)\n",
    "\n",
    "            if l == 0:\n",
    "                for n in range(len(ns) // 2):\n",
    "                    ns[n].val, ns[len(ns) - n - 1].val = ns[len(ns) - n - 1].val, ns[n].val\n",
    "\n",
    "            l ^= 1\n",
    "            s = ns\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # depth = 0\n",
    "        # nodes = [root]\n",
    "        # while nodes:\n",
    "        #     temp = []\n",
    "        #     for node in nodes:\n",
    "        #         if node.left:\n",
    "        #             temp.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             temp.append(node.right)\n",
    "        #     if depth % 2:\n",
    "        #         val = [i.val for i in nodes][::-1]\n",
    "        #         for i in range(len(nodes)):\n",
    "        #             nodes[i].val = val[i]\n",
    "        #     nodes = temp\n",
    "        #     depth += 1\n",
    "        # return root\n",
    "\n",
    "        # ------------------------------------\n",
    "        q, level = [root], 0\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            if level == 0:\n",
    "                for i in range(len(q) // 2):\n",
    "                    x, y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            level ^= 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def help(l, r, flag):\n",
    "            if not l:\n",
    "                return\n",
    "            if flag:\n",
    "                l.val, r.val = r.val, l.val\n",
    "            help(l.left, r.right, not flag)\n",
    "            help(l.right, r.left, not flag)\n",
    "        help(root.left, root.right, True)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def rev(left, right, level):\n",
    "            if not left:\n",
    "                return\n",
    "            rev(left.left, right.right, level+1)\n",
    "            rev(left.right, right.left, level+1)\n",
    "            if level%2 == 1:\n",
    "                left.val, right.val = right.val, left.val\n",
    "        rev(root.left, root.right, 1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node1: TreeNode, node2: TreeNode, is_odd_level: bool) -> None:\n",
    "            if node1 is None: return\n",
    "            if is_odd_level: node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not is_odd_level)\n",
    "            dfs(node1.right, node2.left, not is_odd_level)\n",
    "        dfs(root.left, root.right, True)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, level = [root], 0\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            if level == 0:\n",
    "                for i in range(len(q) // 2):\n",
    "                    x, y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            level ^= 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1, node2, is_odd_level):\n",
    "            if node1 is None:\n",
    "                return\n",
    "            if is_odd_level:\n",
    "                node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not is_odd_level)\n",
    "            dfs(node1.right, node2.left, not is_odd_level)\n",
    "        \n",
    "        dfs(root.left, root.right, True)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1,node2,is_ood_level):\n",
    "            if not node1:\n",
    "                return\n",
    "            if is_ood_level:\n",
    "                node1.val,node2.val = node2.val,node1.val\n",
    "            dfs(node1.left,node2.right,not is_ood_level)\n",
    "            dfs(node1.right,node2.left,not is_ood_level)\n",
    "        dfs(root.left,root.right,True)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "        isOdd = False\n",
    "        while len(q) > 0:\n",
    "            if isOdd:\n",
    "                for i in range (len(q) // 2):\n",
    "                    nodex, nodey = q[i], q[len(q) - 1 - i]\n",
    "                    nodex.val, nodey.val = nodey.val, nodex.val\n",
    "\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.left is not None:\n",
    "                    q.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    q.append(node.right)       \n",
    "            isOdd ^= True\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = [root]\n",
    "        level = 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            level += 1\n",
    "            for a in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                tmp.append(node)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                    queue.append(node.right)\n",
    "            if level % 2 == 0:\n",
    "                for a in range(int(len(tmp) / 2)):\n",
    "                    tmp[a].val, tmp[-(a + 1)].val = tmp[-(a + 1)].val, tmp[a].val\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, level = [root], 0\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            if level == 0:\n",
    "                for i in range(len(q) // 2):\n",
    "                    x, y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            level ^= 1\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "        isOdd = False\n",
    "        while len(q) > 0:\n",
    "            if isOdd:\n",
    "                for i in range (len(q) // 2):\n",
    "                    nodex, nodey = q[i], q[len(q) - 1 - i]\n",
    "                    nodex.val, nodey.val = nodey.val, nodex.val\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.left is not None:\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)                           \n",
    "            isOdd ^= True\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "        isOdd = False\n",
    "        while len(q) > 0:\n",
    "            if isOdd:\n",
    "                for i in range (len(q) // 2):\n",
    "                    nodex, nodey = q[i], q[len(q) - 1 - i]\n",
    "                    nodex.val, nodey.val = nodey.val, nodex.val\n",
    "\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.left is not None:\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)                           \n",
    "            isOdd ^= True\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, level = [root], 0\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            if level == 0:\n",
    "                for i in range(len(q) // 2 ):\n",
    "                    x,y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val  = y.val, x.val\n",
    "            level ^= 1\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # ans = []\n",
    "        # q = deque()\n",
    "        # q.append(root)\n",
    "        # layer = 0\n",
    "\n",
    "        # while q:\n",
    "        #     n = len(q)\n",
    "        #     tmp = []\n",
    "        #     for i in range(n):\n",
    "        #         node = q.popleft()\n",
    "        #         if node:\n",
    "        #             tmp.append(node.val)\n",
    "        #             q.append(node.left)\n",
    "        #             q.append(node.right)\n",
    "        #     if layer % 2 == 1:\n",
    "        #         tmp = tmp[::-1]\n",
    "        #     layer += 1\n",
    "        #     ans += tmp\n",
    "\n",
    "        # q = deque()\n",
    "        # q.append(root)\n",
    "        # idx = 0\n",
    "        # while q:\n",
    "        #     node = q.popleft()\n",
    "        #     if node:\n",
    "        #         node.val = ans[idx]\n",
    "        #         idx += 1\n",
    "        #         q.append(node.left)\n",
    "        #         q.append(node.right)\n",
    "        # return root\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1: Optional[TreeNode], node2: Optional[TreeNode], is_odd_level: bool) -> None:\n",
    "            if node1 is None: return\n",
    "            if is_odd_level: node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not is_odd_level)\n",
    "            dfs(node1.right, node2.left, not is_odd_level)\n",
    "        dfs(root.left, root.right, True)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        dueue=[root]\n",
    "        level=1\n",
    "\n",
    "        while dueue[0].left:\n",
    "            temp=[]\n",
    "            for q in dueue:\n",
    "                temp.append(q.left)\n",
    "                temp.append(q.right)\n",
    "            \n",
    "            level+=1\n",
    "            dueue=temp\n",
    "            if level % 2==0: #交换\n",
    "                l=len(dueue)\n",
    "                for i in range(l//2):\n",
    "                    dueue[i].val,dueue[l-i-1].val=dueue[l-i-1].val,dueue[i].val\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "        depth = 0\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            if depth%2 == 0:\n",
    "                for i in range(len(q) // 2):\n",
    "                    left, right = q[i], q[len(q)-1-i]\n",
    "                    left.val, right.val = right.val, left.val\n",
    "            depth += 1\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "        level = 0\n",
    "        while q:\n",
    "            if level % 2:\n",
    "                for i in range(len(q) // 2):\n",
    "                    q[i].val, q[len(q) - i - 1].val = q[len(q) - i - 1].val, q[i].val\n",
    "            tmp = q\n",
    "            q = []        \n",
    "            for node in tmp:\n",
    "                if node.left: \n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            level += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, floor = [root], 0\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            if floor == 0:\n",
    "               for i in range(len(q) // 2):\n",
    "                   x, y = q[i], q[len(q) - 1 - i]\n",
    "                   x.val, y.val = y.val, x.val\n",
    "            floor ^= 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, level = [root], True\n",
    "        while q[0].left:\n",
    "            q = [*chain.from_iterable((node.left, node.right) for node in q)]\n",
    "            if level:\n",
    "                for i in range(len(q) // 2):\n",
    "                    x, y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            level = not level\n",
    "        return root\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode], depth = 0) -> Optional[TreeNode]:\n",
    "        def dfs(node1, node2, reverse):\n",
    "            if node1 is None: return\n",
    "\n",
    "            if reverse: node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not reverse)\n",
    "            dfs(node1.right, node2.left, not reverse)\n",
    "\n",
    "        dfs(root.left, root.right, True)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, level = [root], 0\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left,node.right) for node in q))\n",
    "            if level == 0:\n",
    "                for i in range(len(q) >> 1):\n",
    "                    x, y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            level ^= 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return\n",
    "        queue = [root]\n",
    "        is_odd = False\n",
    "        while queue:\n",
    "            layer = []\n",
    "            n = len(queue)\n",
    "            for _ in range(n):\n",
    "                node = queue.pop(0)\n",
    "                layer.append(node)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            if is_odd:\n",
    "                left = 0\n",
    "                right = n - 1\n",
    "                while left < right:\n",
    "                    layer[left].val, layer[right].val = layer[right].val, layer[left].val\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "            is_odd = not is_odd\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(node1,node2,flag):\n",
    "            if node1 is None:return\n",
    "            if flag:\n",
    "                node1.val,node2.val=node2.val,node1.val\n",
    "            dfs(node1.left,node2.right,flag= not flag)\n",
    "            dfs(node1.right,node2.left,flag=not flag)\n",
    "        dfs(root.left,root.right,True)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1: Optional[TreeNode], node2: Optional[TreeNode], is_odd_level: bool) -> None:\n",
    "            if node1 is None: return\n",
    "            if is_odd_level: node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not is_odd_level)\n",
    "            dfs(node1.right, node2.left, not is_odd_level)\n",
    "        dfs(root.left, root.right, True)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, level = [root], 0\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            if level == 0:\n",
    "                for i in range(len(q) // 2):\n",
    "                    x, y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            level ^= 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1, node2, isOdd):\n",
    "            if node1 is None:\n",
    "                return\n",
    "            if isOdd:\n",
    "                node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not isOdd)\n",
    "            dfs(node1.right, node2.left, not isOdd)\n",
    "        dfs(root.left, root.right, True)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(left, right, odd):\n",
    "            if not left:\n",
    "                return\n",
    "            if odd:\n",
    "                left.val, right.val = right.val, left.val\n",
    "            dfs(left.left, right.right, not odd)\n",
    "            dfs(left.right, right.left, not odd)\n",
    "        dfs(root.left, root.right, True)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # bfs\n",
    "        # q = deque([root])\n",
    "        # odd_flag = True\n",
    "        # while q:\n",
    "        #     sz = len(q)\n",
    "        #     lv_nodes = []\n",
    "        #     for i in range(sz):\n",
    "        #         node = q.popleft()\n",
    "        #         if node.left: lv_nodes.append(node.left)\n",
    "        #         if node.right: lv_nodes.append(node.right)\n",
    "        #     q.extend(lv_nodes)\n",
    "        #     if odd_flag:\n",
    "        #         for i in range(len(q)//2):\n",
    "        #             x,y = q[i],q[len(q)-1-i]\n",
    "        #             x.val,y.val = y.val,x.val\n",
    "        #     odd_flag = not odd_flag\n",
    "        # return root\n",
    "        # dfs\n",
    "        self.dfs(root.left,root.right, True)\n",
    "        return root\n",
    "    \n",
    "    def dfs(self,a,b,level):\n",
    "        if not a or not b:\n",
    "            return\n",
    "        if level:\n",
    "            a.val,b.val = b.val,a.val\n",
    "        self.dfs(a.left,b.right, not level)\n",
    "        self.dfs(a.right,b.left, not level)\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root1: Optional[TreeNode], root2 : Optional[TreeNode], isOdd : bool) -> None:\n",
    "            if root1 is None:\n",
    "                return\n",
    "            if isOdd:\n",
    "                root1.val, root2.val = root2.val, root1.val\n",
    "            dfs(root1.left, root2.right, not isOdd)\n",
    "            dfs(root1.right, root2.left, not isOdd)\n",
    "        dfs(root.left, root.right, True)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1: Optional[TreeNode], node2: Optional[TreeNode], is_odd_level: bool) -> None:\n",
    "            if node1 is None: return\n",
    "            if is_odd_level: node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not is_odd_level)\n",
    "            dfs(node1.right, node2.left, not is_odd_level)\n",
    "        dfs(root.left, root.right, True)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        \n",
    "        q = collections.deque([root])\n",
    "        \n",
    "        level = 0\n",
    "        while any(q):\n",
    "            cur = list(q)\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                q.append(node.left if node else None)\n",
    "                q.append(node.right if node else None)\n",
    "            \n",
    "            if level % 2:\n",
    "                cur = cur[::-1]\n",
    "                nxt = q\n",
    "            else:\n",
    "                nxt = list(q)[::-1]\n",
    "                \n",
    "            for i, node in enumerate(cur):\n",
    "                node.left = nxt[i*2]\n",
    "                node.right = nxt[i*2+1]\n",
    "                \n",
    "            level += 1\n",
    "            \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1: Optional[TreeNode], node2: Optional[TreeNode], is_odd_level: bool) -> None:\n",
    "            if node1 is None: return\n",
    "            if is_odd_level: node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not is_odd_level)\n",
    "            dfs(node1.right, node2.left, not is_odd_level)\n",
    "        \n",
    "        dfs(root.left, root.right, True)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        s = [root]\n",
    "        l = 1\n",
    "        while s:\n",
    "            ns = []\n",
    "            nss = []\n",
    "            for i in s:\n",
    "                if i.left:\n",
    "                    ns.append(i.left)\n",
    "                    ns.append(i.right)\n",
    "                    if l % 2 == 1:\n",
    "                        nss.append(i.left.val)\n",
    "                        nss.append(i.right.val)\n",
    "\n",
    "            if l % 2 == 1:\n",
    "                for n in ns:\n",
    "                    n.val = nss.pop()\n",
    "\n",
    "            l = l + 1\n",
    "            s = ns\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # bfs\n",
    "        l = [root]\n",
    "        odd = False\n",
    "        while l:\n",
    "            if odd: # 反转值\n",
    "                v = [n.val for n in l[::-1]]\n",
    "                for n, new in zip(l, v):\n",
    "                    n.val = new\n",
    "                    \n",
    "            odd = not odd\n",
    "            l2 = []\n",
    "            for n in l:\n",
    "                if n.left:\n",
    "                    l2.append(n.left)\n",
    "                if n.right:\n",
    "                    l2.append(n.right)\n",
    "            l = l2\n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import chain\n",
    "from typing import Optional\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 初始化队列和层级标志\n",
    "        q, level = [root], 0\n",
    "\n",
    "        # 遍历每一层的节点\n",
    "        while q[0].left:\n",
    "            # 将当前层的所有左右子节点加入到队列中\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            \n",
    "            # 如果当前层是奇数层，则反转该层的节点值\n",
    "            if level == 0:\n",
    "                for i in range(len(q) // 2):\n",
    "                    x, y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            \n",
    "            # 更新层级标志（0 和 1 之间切换，以标记奇偶层）\n",
    "            level ^= 1\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = deque([root])\n",
    "        is_odd = True\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                top = queue.popleft()\n",
    "                if top.left:\n",
    "                    queue.append(top.left)\n",
    "                if top.right:\n",
    "                    queue.append(top.right)\n",
    "            if is_odd:\n",
    "                for i in range(len(queue) // 2):\n",
    "                    tmp = queue[i].val\n",
    "                    queue[i].val = queue[-(i + 1)].val\n",
    "                    queue[-(i + 1)].val = tmp\n",
    "            is_odd = not is_odd\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, level = [root], 0\n",
    "        while q[0].left:\n",
    "            q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "            if level == 0:\n",
    "                for i in range(len(q) // 2):\n",
    "                    x, y = q[i], q[len(q) - 1 - i]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            level ^= 1\n",
    "        return root\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        node_lst = [root]\n",
    "        flag = True\n",
    "        while node_lst:\n",
    "            tmp_lst = []\n",
    "            for node in node_lst:\n",
    "                if node.left:\n",
    "                    tmp_lst.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp_lst.append(node.right)\n",
    "            if flag:\n",
    "                for i in range(len(tmp_lst) // 2):\n",
    "                    tmp_val = tmp_lst[i].val\n",
    "                    tmp_lst[i].val = tmp_lst[len(tmp_lst) - 1 - i].val\n",
    "                    tmp_lst[len(tmp_lst) - 1 - i].val = tmp_val\n",
    "                flag = False\n",
    "            else:\n",
    "                flag = True\n",
    "            node_lst = tmp_lst[:]\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        nodes = [root]\n",
    "        lv = 0\n",
    "        while nodes:\n",
    "            new_nodes = []\n",
    "            for x in nodes:\n",
    "                if x.left:\n",
    "                    new_nodes.append(x.left)\n",
    "                if x.right:\n",
    "                    new_nodes.append(x.right)\n",
    "                \n",
    "            if lv%2==1 and lv>0:\n",
    "                for a,b in zip(nodes,[x.val for x in nodes[::-1]]):\n",
    "                    a.val=b\n",
    "            nodes = new_nodes\n",
    "            lv+=1\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "        d = 0\n",
    "        while q:\n",
    "            nq = []\n",
    "            n = len(q)\n",
    "            l, r = 0, n - 1\n",
    "            while d & 1 and l < r:\n",
    "                q[l].val, q[r].val = q[r].val, q[l].val\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            for tn in q:\n",
    "                if tn.left:\n",
    "                    nq.append(tn.left) \n",
    "                if tn.right:\n",
    "                    nq.append(tn.right)\n",
    "            q = nq\n",
    "            d += 1\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(n1, n2, k):\n",
    "            pass\n",
    "            if not n1:\n",
    "                return \n",
    "            # if root.left:\n",
    "            \n",
    "            # root.left, root.right = root.right , root.left\n",
    "            # dfs(root.left, k+1)\n",
    "            # dfs(root.right, k+1)\n",
    "            # # root.left.val, root.right.val = root.right.val, root.left.val\n",
    "            \n",
    "            # if k % 2 == 1:\n",
    "            #     root.left.val, root.right.val = root.right.val, root.left.val\n",
    "            #     # root.left, root.right = root.right , root.left\n",
    "            # # if k % 2 == 1:\n",
    "\n",
    "            # dfs(root.left, k+1)\n",
    "            # dfs(root.right, k+1)\n",
    "            if k % 2 == 0:\n",
    "                n1.val, n2.val = n2.val, n1.val\n",
    "            dfs(n1.left, n2.right, k+1)\n",
    "            dfs(n1.right, n2.left, k+1)\n",
    "            \n",
    "        \n",
    "        dfs(root.left, root.right, 0)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        s = [root]\n",
    "        l = 0\n",
    "        while s[0].left:\n",
    "            ns = []\n",
    "            nss = []\n",
    "            for i in s:\n",
    "                ns.append(i.left)\n",
    "                ns.append(i.right)\n",
    "                if l == 0:\n",
    "                    nss.append(i.left.val)\n",
    "                    nss.append(i.right.val)\n",
    "\n",
    "            if l == 0:\n",
    "                for n in ns:\n",
    "                    n.val = nss.pop()\n",
    "\n",
    "            l ^= 1\n",
    "            s = ns\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = collections.deque([root])\n",
    "        step = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            tmp = []\n",
    "\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                    if step % 2 == 0:\n",
    "                        tmp.append(node.left.val)\n",
    "\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                    if step % 2 == 0:\n",
    "                        tmp.append(node.right.val)\n",
    "\n",
    "\n",
    "            if step % 2 == 0:\n",
    "                for node, val in zip(queue, tmp[::-1]):\n",
    "                    node.val = val\n",
    "\n",
    "            step += 1\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        st = deque([root])\n",
    "        f = False\n",
    "        while st:\n",
    "            l = len(st)\n",
    "            tmp = []\n",
    "            nums = []\n",
    "            for i in range(l):\n",
    "                node = st.popleft()\n",
    "                if f:\n",
    "                    nums.append(node.val)\n",
    "                    tmp.append(node)\n",
    "                if node.left:\n",
    "                    st.append(node.left)\n",
    "                if node.right:\n",
    "                    st.append(node.right)\n",
    "            if f:\n",
    "                for n in nums:\n",
    "                    node = tmp.pop()\n",
    "                    node.val = n\n",
    "            f = not f\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1: Optional[TreeNode], node2: Optional[TreeNode], is_odd_level: bool)->None:\n",
    "            if node1 is None:\n",
    "                return\n",
    "            if is_odd_level: node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not is_odd_level)\n",
    "            dfs(node1.right, node2.left, not is_odd_level)\n",
    "        dfs(root.left, root.right, True)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        i = 0\n",
    "        if not root:\n",
    "            return root\n",
    "        ans = root\n",
    "        l = [root]\n",
    "        temp = []\n",
    "        while l:\n",
    "            while l:\n",
    "                node = l.pop(0)\n",
    "                if node.left:\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    temp.append(node.right)\n",
    "            \n",
    "            l = temp\n",
    "            if i % 2 == 0:\n",
    "                for j in range(len(temp)//2):\n",
    "                    temp[j].val, temp[len(temp)-j-1].val = temp[len(temp)-j-1].val, temp[j].val\n",
    "            temp = []\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return None\n",
    "        q = collections.deque([root])\n",
    "        even = False\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            if even :\n",
    "                left = 0\n",
    "                right = n-1\n",
    "                while left <= right:\n",
    "                    q[left].val, q[right].val = q[right].val, q[left].val\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "            for i in range(n):\n",
    "                node = q.popleft()\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right) \n",
    "            even = not even\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        path = [root]\n",
    "        flag = False\n",
    "        while path:\n",
    "            to_path = []\n",
    "            for node in path:\n",
    "                if node.left:to_path.append(node.left)\n",
    "                if node.right:to_path.append(node.right)\n",
    "            if flag:\n",
    "                n = len(path)\n",
    "                for i in range(n//2):\n",
    "                    path[i].val, path[n-i-1].val = path[n-i-1].val, path[i].val\n",
    "            flag ^= True\n",
    "            path = to_path\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.dfs(root.left, root.right, 1)\n",
    "        return root\n",
    "\n",
    "    def dfs(self, l,r,depth):\n",
    "        if l == None or r == None:\n",
    "            return\n",
    "        if depth % 2 ==1:\n",
    "            temp = l.val\n",
    "            l.val = r.val\n",
    "            r.val = temp\n",
    "        self.dfs(l.left, r.right, depth +1)\n",
    "        self.dfs(l.right, r.left, depth +1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        q = [root]\n",
    "        level = 0\n",
    "        head, tail = 0, 1\n",
    "        while head < tail:\n",
    "            for now in q[head : tail]:\n",
    "                if now.left:\n",
    "                    q.append(now.left)\n",
    "                    q.append(now.right)\n",
    "            \n",
    "            if level % 2 == 1:\n",
    "                l, r = head, tail - 1\n",
    "                while l < r:\n",
    "                    q[l].val, q[r].val = q[r].val, q[l].val\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "            \n",
    "            head, tail = tail, len(q)\n",
    "            level += 1\n",
    "        \n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # depth = 0\n",
    "        # nodes = [root]\n",
    "        # while nodes:\n",
    "        #     temp = []\n",
    "        #     for node in nodes:\n",
    "        #         if node.left:\n",
    "        #             temp.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             temp.append(node.right)\n",
    "        #     if depth % 2:\n",
    "        #         val = [i.val for i in nodes][::-1]\n",
    "        #         for i in range(len(nodes)):\n",
    "        #             nodes[i].val = val[i]\n",
    "        #     nodes = temp\n",
    "        #     depth += 1\n",
    "        # return root\n",
    "\n",
    "        # ------------------------------------\n",
    "        # q, level = [root], 0\n",
    "        # while q[0].left:\n",
    "        #     q = list(chain.from_iterable((node.left, node.right) for node in q))\n",
    "        #     if level == 0:\n",
    "        #         for i in range(len(q) // 2):\n",
    "        #             x, y = q[i], q[len(q) - 1 - i]\n",
    "        #             x.val, y.val = y.val, x.val\n",
    "        #     level ^= 1\n",
    "        # return root\n",
    "\n",
    "        # --------------------------------\n",
    "        def tarverse(node1, node2, is_odd_flag):\n",
    "            if not node1:\n",
    "                return \n",
    "            if is_odd_flag:\n",
    "                node1.val, node2.val = node2.val, node1.val \n",
    "            tarverse(node1.left, node2.right, not is_odd_flag)\n",
    "            tarverse(node1.right, node2.left, not is_odd_flag)\n",
    "        \n",
    "        tarverse(root.left, root.right, True)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        \n",
    "        q = collections.deque([root])\n",
    "        \n",
    "        level = 0\n",
    "        while any(q):\n",
    "            cur = list(q)\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                q.append(node.left if node else None)\n",
    "                q.append(node.right if node else None)\n",
    "            \n",
    "            if level % 2:\n",
    "                cur = cur[::-1]\n",
    "                nxt = q\n",
    "            else:\n",
    "                nxt = list(q)[::-1]\n",
    "                \n",
    "            for i, node in enumerate(cur):\n",
    "                node.left = nxt[i*2]\n",
    "                node.right = nxt[i*2+1]\n",
    "                \n",
    "            level += 1\n",
    "            \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        cache = {}\n",
    "        self.traversal(root, cache, 0)\n",
    "        level = 0\n",
    "        while cache.get(level) is not None:\n",
    "            if level % 2 == 1:\n",
    "                node_list = cache[level]\n",
    "                left = 0\n",
    "                right = len(node_list)-1\n",
    "                while left<right:\n",
    "                    node_list[left].val, node_list[right].val = node_list[right].val, node_list[left].val\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "            level += 1\n",
    "        return root\n",
    "\n",
    "    def traversal(self, node, cache, level):\n",
    "        if node is None:\n",
    "            return\n",
    "        self.traversal(node.left, cache, level+1)\n",
    "        if cache.get(level) is None:\n",
    "            cache[level] = [node]\n",
    "        else:\n",
    "            cache[level].append(node)\n",
    "        self.traversal(node.right, cache, level+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "  \n",
    "\n",
    "        # 初始化队列，元素为根节点\n",
    "        queue = collections.deque([root])\t\n",
    "        level = 0\n",
    "\n",
    "        # 当队列非空时\n",
    "        while queue:\n",
    "            if level % 2 == 1:\n",
    "                i, j = 0, len(queue) - 1\n",
    "                while i < j:\n",
    "                    queue[i].val, queue[j].val = queue[j].val, queue[i].val\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "            level += 1\n",
    "            # 依次从队列中取出该层节点拓展\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\t     # 队首的节点出队\n",
    "\n",
    "                # 如果节点的左/右子树不为空，也放入队列中\n",
    "                if node.left: \n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution: \n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        nodes = [root]\n",
    "        # out = []\n",
    "        depth = 0\n",
    "        while nodes:\n",
    "            temp = []\n",
    "            # out_t = []\n",
    "            if depth%2 == 1:\n",
    "                l = len(nodes)\n",
    "                for i in range(l//2):\n",
    "                    nodes[i].val,nodes[l-i-1].val = nodes[l-i-1].val,nodes[i].val\n",
    "            for node in nodes:\n",
    "                if node.left:\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    temp.append(node.right)\n",
    "                # out_t.append(node.val)\n",
    "            depth += 1\n",
    "            nodes = temp\n",
    "            # out += [out_t]\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        def dfs(node, d):\n",
    "            if not node:\n",
    "                return\n",
    "            dic[d].append(node.val)\n",
    "            dfs(node.left, d + 1)\n",
    "            dfs(node.right, d + 1)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "\n",
    "        def re(node, d):\n",
    "            if not node:\n",
    "                return\n",
    "            if d % 2 == 1:\n",
    "                node.val = dic[d].pop()\n",
    "            re(node.left, d + 1)\n",
    "            re(node.right, d + 1)\n",
    "        \n",
    "        re(root, 0)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        level_map = {}\n",
    "        level = 0\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            stack = []\n",
    "            while queue:\n",
    "                stack.append(queue.pop(0))\n",
    "            while stack:\n",
    "                node = stack.pop(0)\n",
    "                if level not in level_map.keys():\n",
    "                    level_map[level] = []\n",
    "                level_map[level].append(node)\n",
    "                if node.left is not None:\n",
    "                    queue.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    queue.append(node.right)\n",
    "            level += 1\n",
    "        # print(\"levelmap=\", level_map)\n",
    "        # 交换奇数层的值\n",
    "        for l, vals in level_map.items():\n",
    "            if l % 2 == 0:\n",
    "                continue\n",
    "            left, right = 0, vals.__len__() - 1\n",
    "            print(\"len=\", vals.__len__())\n",
    "            while left < right:\n",
    "                vals[left].val, vals[right].val = vals[right].val, vals[left].val\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node1, node2, is_odd_level):\n",
    "            if node1 is None:\n",
    "                return \n",
    "            if is_odd_level:\n",
    "                node1.val, node2.val = node2.val, node1.val\n",
    "            dfs(node1.left, node2.right, not is_odd_level)\n",
    "            dfs(node1.right, node2.left, not is_odd_level)\n",
    "        dfs(root.left, root.right, True)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # bfs\n",
    "        q = deque([root])\n",
    "        odd_flag = True\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            lv_nodes = []\n",
    "            for i in range(sz):\n",
    "                node = q.popleft()\n",
    "                if node.left: lv_nodes.append(node.left)\n",
    "                if node.right: lv_nodes.append(node.right)\n",
    "            q.extend(lv_nodes)\n",
    "            if odd_flag:\n",
    "                for i in range(len(q)//2):\n",
    "                    x,y = q[i],q[len(q)-1-i]\n",
    "                    x.val,y.val = y.val,x.val\n",
    "            odd_flag = not odd_flag\n",
    "        return root\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        q = deque([root])\n",
    "        res = []\n",
    "        while q:\n",
    "            vals = []\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                vals.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            res.append(vals)\n",
    "        q = deque([root])\n",
    "        even = False\n",
    "        j = 1\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if even: node.val = res[j][-i-1] \n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            if even:j+=2\n",
    "            even = not even\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        q = deque([root])\n",
    "\n",
    "        even = False\n",
    "        while q:\n",
    "            d = q.copy()\n",
    "            n = len(q) \n",
    "            for i in range(n):\n",
    "                node = q.popleft()\n",
    "                node1 = d.pop()\n",
    "                if even and  i < (n)/2: \n",
    "                    node.val,node1.val = node1.val ,node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            even = not even\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        q = [root]\n",
    "        level = 1\n",
    "        while q[0].left:\n",
    "            nxt = []\n",
    "            for node in q:\n",
    "                nxt += [node.left, node.right]\n",
    "            q = nxt\n",
    "            if level:\n",
    "                for i in range(len(q)//2):\n",
    "                    x, y = q[i], q[len(q)-i-1]\n",
    "                    x.val, y.val = y.val, x.val\n",
    "            level ^= 1\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
